1. Technical Field
The present invention relates to searching for an object in a particular set to determine whether the object belongs to the particular set, more specifically to searching for an object in a particular set to determine whether the object belongs to the particular set through a bloom filter using orthogonal codes.
2. Background Art
A bloom filter is a data structure indicating that a specific object is present in a particular set by inputting an identifier or details of objects in a hash function, compressing the identifier or details of objects to a predetermined size and storing the identifier or details of objects in a sequence expressed with 1 and 0. That is, in order to check whether the object is present within the bloom filter, it is determined whether an output value resulted from inputting the identifier or details of the object in the hash function is stored with 1 in the bloom filter. The bloom filter is utilized for spelling check, dictionary search, web search, etc. Especially, in the case of an LISP (Locator Identifier Separation Protocol) system, the bloom filter has stored therein information of a set of identifiers of objects that are serviced by a specific router (i.e., Egress Tunnel Router).